// 给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。
// 本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

function sortedListToBST(head: ListNode | null): TreeNode | null {
    if (!head) {// 递归出口
        return null;
    }
    // 快慢指针找中点
    let slow: ListNode | null = head;
    let fast: ListNode | null = head;
    let prev: ListNode | null = null;// 前驱节点
    while (fast && fast.next) {
        prev = slow;
        slow = slow?.next;
        fast = fast.next.next;
    }// 此时的slow已经是中点
    const root: TreeNode = new TreeNode(slow.val);
    if (prev !== null) {// 如果prev存在，断开链表分治，构造左子树
        prev.next = null as any;// 断开链表
        root.left = sortedListToBST(head);
    }
    root.right = sortedListToBST(slow.next); // 构造右子树
    return root;
};

// 这道题也是一道值得学习的例题，
// 掌握了方法后其实并没有想象中的有难度。
// 首先我们把有序链表想象成一根绳子:
// 我们提起绳子中点作为根节点，分出中点把绳子砍成左右两部分，
// 再提起各自的中点作为根节点同样进行上述操作，不断分治，这根绳就成了 BST 的模样。
// 这道题的一个处理点在于要定位到有序链表的中点，
// 而这其实也是一个老生常谈的问题，这里用一个快慢指针方法，就可以在每一轮次定位到指针的中点
// 为了断开成两部分，我们需要一个指针记录慢指针的前一个节点，因为单向链表的节点没有前驱指针。
// 然后我们以中点作为树的根节点开始构造，当前驱节点存在时，说明左子树尚未构造完成
// 我们断开链表分支，继续以头节点做左子树构造
// 左子树构造完成后就以中点节点的下一个节点为头节点开始构造右子树
// 当左右子树构造完成后，返回根节点就得到了我们想要的平衡二叉树。


